halting problem

停止性問題

計算可能性理論において停止(性)問題（ていしせいもんだい・ていしもんだい、halting problem）は、

あるチューリングマシン（≒コンピュータプログラム・アルゴリズム）が、

そのテープのある初期状態（≒入力）に対し、有限時間で停止するか、という問題。

アラン・チューリングが1936年、停止性問題を解くチューリング機械が存在しない事をある種の対角線論法のようにして証明した。

すなわち、そのようなチューリング機械の存在を仮定すると

「自身が停止すると判定したならば無限ループを行い、停止しないと判定したならば停止する」

ような別のチューリング機械が構成でき、矛盾となる。